package com.shuang.greed16;

public class MonotoneIncreasingDigits {
    //从后向前遍历(从前向后遍历的话会出现 前一个位置减一后比更之前的位置又小了 例如332模拟一下) 如果前一个位置数比当前位置的数大（不满足递增） 把前面的数字减一 当前位置的数字改为9即可
    public int monotoneIncreasingDigits(int n) {
        //将数字n变成字符串后转为字符数组操作
        String s = String.valueOf(n);
        char[] chars = s.toCharArray();

        //用于标记的变量 从该位置往后所有数字都变成9 ()
        int flag = chars.length;

        //从后向前遍历数组
        for (int i = chars.length - 1; i > 0; i--) {
            //判断前一个位置和当前位置大小
            if (chars[i - 1] > chars[i]) {
                //不满足递增
                //前一个位置减一 当前位置标记
                chars[i - 1]--;
                flag = i;
            }
        }

        //将从标记位置往后都变成9
        for (int i = flag; i < chars.length; i++){
            chars[i] = '9';
        }

        return Integer.parseInt(String.valueOf(chars));
    }
}
